package practise;

public class IsBalanced {
/*    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public static int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        //得到左树与右树的较大者 再加上 本身(1)
        return Math.max(maxDepth(root.right), maxDepth(root.left)) + 1;
    }*/

    /*
        在遍历求最大深度的同时判断是否是平衡树
        如果是就返回最大深度
        不是就返回 -1
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
       /* int rightHigh,leftHigh;

        if((leftHigh = maxDepth(root.left)) == -1) {
            return false;
        }
        if((rightHigh = maxDepth(root.right)) == -1) {
            return false;
        }
        return Math.abs(leftHigh - rightHigh) <= 1;*/
        return maxDepth(root) >= 0;
    }

    public static int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHigh;
        int rightHigh;
        //如果为 -1 那么就是不平衡
        if((leftHigh = maxDepth(root.right)) == -1 ||
                (rightHigh = maxDepth(root.left)) == -1 ||
                Math.abs(leftHigh - rightHigh) > 1){
            return -1;
        }

        //得到左树与右树的较大者 再加上 本身(1)
        return Math.max(leftHigh, rightHigh) + 1;
    }
}
